package LRU;

import java.util.HashMap;

public class LRUCache {
    public class Node{
        int key;
        int val;
        Node pre;
        Node next;
        Node(){}
        Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
    private int cap;
    private Node dummy = new Node(-1, -1);
    private HashMap<Integer, Node> map = new HashMap<>();
    public LRUCache(int cap){
        this.cap = cap;
        dummy.next = dummy;
        dummy.pre = dummy;
    }
    public int get(int key){
        Node node = map.get(key);
        if(node == null) return -1;
        move2Head(node);
        return node.val;
    }
    public void put(int key, int val){
        Node node = map.get(key);
        if(node != null){
            node.val = val;
            move2Head(node);
        } else {
            Node newNode = new Node(key, val);
            add2Head(newNode);
            map.put(key, newNode);
            if(map.size() > cap){
                Node lastNode = removeTail();
                map.remove(lastNode.key);
            }
        }
    }
    private void move2Head(Node node){
        removeNode(node);
        add2Head(node);
    }
    private void removeNode(Node node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }
    private Node removeTail(){
        Node lastNode = dummy.pre;
        removeNode(lastNode);
        return lastNode;
    }
    private void add2Head(Node node){
        node.next = dummy.next;
        dummy.next.pre = node;
        dummy.next = node;
        node.pre = dummy;
    }
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
    }
}
